//和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。 
//
// 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。 
//
// 数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,2,2,5,2,3,7]
//输出：5
//解释：最长的和谐子序列是 [3,2,2,2,3]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4]
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,1,1,1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 104 
// -109 <= nums[i] <= 109 
// 
// Related Topics 数组 哈希表 排序 
// 👍 194 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LongestHarmoniousSubsequence {
    public static void main(String[] args) {
        Solution solution = new LongestHarmoniousSubsequence().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * u1s1，一开始我是一点头绪都没有，以下这种方法纯属巧合凑上了，这个方法也不是不成，题解也有这么写的
     * 思路是这样的：先将数组进行排序，排序之后要是有相同的元素也就连续了
     * i代表可能的和谐数组的长度值-1，i的取值是1到num.length-1，即最短的和谐数组只有两个元素，最长的包含了所有元素
     * j代表的是数组元素的下标，这里需要对数组进行一次遍历，遍历的时候是根据i来进行的，比如i=1的时候只关注j和j+1的元素差
     * i如果=num.length -1 的话则是说明在测试所有元素是否构成和谐数组
     * 突然想到的一个小优化：从i为最大时开始迭代，如果满足条件直接返回就行了，不用继续遍历了，md时间上没有区别
     *
     * 题解中的方法：使用map存储元素出现的次数，对key进行排序
     * 比较两个相邻key差值是否为1，为1的话就次数相加并与max进行比较
     * 因为map的key会自动进行排序，所以只要判断相邻两个key的差值就行了
     */
    public int findLHS(int[] nums) {
        /**
         * 方法一：使用hash匹配
         */
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0)+1);//统计元素出现的个数
        int res = 0;//最终结果
        for (int key : map.keySet()){
            //如果存在连续的key就尝试进行统计
            if (map.containsKey(key+1)) res = Math.max(res,map.get(key) + map.get(key+1) );
        }
        /**
         * 方法二：尺取法，只看头尾
         */
        Arrays.sort(nums);
        for (int i = nums.length-1; i > 0 ; i--) {
            for (int j = 0; j < nums.length - i ; j++) {
                if (nums[j+i] - nums[j] == 1) return i+1;
            }
        }
        return 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}